package com.hh.demo;

import javax.swing.*;

class Element implements Comparable<Object>{
    int w;//集装箱的重量
    int i;//集装箱编号
    public Element(int w, int i) {
        super();//调用基类中的某一个构造函数
        this.w = w;
        this.i = i;
    }
    @Override
    public int compareTo(Object obj) {//Object 是所有类的父亲
        float weight=((Element) obj).w;
        if(w<weight) {
            return -1;
        }
        if(w==weight) {
            return 0;
        }
        return 1;
    }
    public int getW() {
        return w;
    }
    public void setW(int w) {
        this.w = w;
    }
    public int getI() {
        return i;
    }
    public void setI(int i) {
        this.i = i;
    }

}

class MergeSort {
    public static void mergeSort(Element nums[],int low,int high){
        if(low<high){//至少有两个元素
            int mid=(low+high)/2;//取中点
            //左边
            mergeSort(nums,low,mid);
            //右边
            mergeSort(nums,mid+1,high);
            //左右归并
            merge(nums,low,mid,high);
        }
    }
    private static void merge(Element[] nums,int low,int mid,int high) {
        //合并c[1:m]和c[m+1:r]到d[l:r]
        int i=low,j=mid+1,k=0;
        Element temp[]=new Element[high-low+1];
        //把数排好序放进temp数组中
        while((i<=mid)&&(j<=high)){
            //把小的的放进temp数组中
            if(nums[i].getW()-nums[j].getW()<=0) {
                temp[k++]=nums[i++];
            } else {
                temp[k++]=nums[j++];
            }
        }
        //若左边的先遍历完，则把右边剩下的放进temp数组中
        while(i<=mid) {
            temp[k++]=nums[i++];
        }
        //若右边的先遍历完，则把左边剩下的放进temp数组中
        while(j<=high) {
            temp[k++]=nums[j++];
        }
//              把temp中的数放回nums数组中
        for(int p = 0;p<temp.length;p++){
            nums[low+p]=temp[p];
        }
    }
}
public class Optimalloading
{
    //最优装载
    /*float c:轮船的载重量,float[] w:第i个集装箱的重量,
     * int[] x:取0或1 0代表不装入集装箱i，1代表装入集装箱i*/
    public static int loading(int c,int[] w,int[] x){

        int n=w.length;//n代表集装箱的个数
        Element[]d=new Element[n];//n个存着集装箱编号和重量的Element元素组成一个数组
        for(int i=0;i<n;i++)//n次循环，给数组中的每一个元素装上值
        {
            d[i]=new Element(w[i], i);
        }
        MergeSort.mergeSort(d,0,d.length-1);//数组中元素按照集装箱重量由小到大排序
        int opt=0;
        for(int i=0;i<n;i++) {
            x[i]=0;//所有集装箱一开始都没有装上船，所以把x置为0
        }
        for(int i=0;i<n&&d[i].w<c;i++){
            x[d[i].i]=1;//相应编号的集装箱的装入标志设为1
            opt++;
            c-=d[i].w;
        }
        return opt;//返回的是装入集装箱的个数
    }

    public Optimalloading() {
        int c=40;
        int[] w={7,35,78,30,10,4,3,2};
        int[] x={0,0,0,0,0,0,0,0};
        System.out.println("最优装载问题");
        System.out.println("最多装入"+loading(c, w, x)+"个集装箱");
        String title="最优装载算法输出";
        JOptionPane.showMessageDialog(null,"最多装入"+loading(c, w, x)+"个集装箱",title,JOptionPane.INFORMATION_MESSAGE);
    }
}
